import java.util.Deque;
import java.util.LinkedList;

public class MaxWater {
    public long maxWater1 (int[] arr) {
        // write code here
        // 用left数组来记录当前元素左边的最高的柱子的高度，right数组记录当前元素右边最高柱子的高度
        int len = arr.length;
        int[] left = new int[len];
        int[] right = new int[len];
        int prev = 0;
        for (int i = 0; i < len; i++) {
            left[i] = prev;
            prev = Math.max(prev, arr[i]);
        }
        prev = 0;
        for (int i = len-1; i >= 0; i--) {
            right[i] = prev;
            prev = Math.max(prev, arr[i]);
        }
        int ret = 0;
        for (int i = 0; i < len; i++) {
            ret += Math.max(Math.min(left[i], right[i])-arr[i], 0);
        }
        return ret;
    }

    public long maxWater (int[] arr) {
        // write code here
        // 通过单调栈来解决，从栈底到栈顶的元素是递减的，当遇到大于栈顶元素的时候，那么当前元素、栈顶元素和栈中的下一个元素之间就能接雨水
        Deque<Integer> deque = new LinkedList<>();
        int ret = 0;
        for (int i = 0; i < arr.length; i++) {
            if (deque.size() > 0 && arr[i] > arr[deque.peekLast()]) {
                while (deque.size() > 0 && arr[i] > arr[deque.peekLast()]) {
                    int mid = deque.pollLast();
                    if (deque.size() == 0) {
                        break;
                    }
                    int left = deque.peekLast();
                    ret += Math.max((Math.min(arr[left], arr[i])- arr[mid]) * (i - left - 1), 0);
                }
            }
            deque.addLast(i);
        }
        return ret;
    }

    public static void main(String[] args) {
        System.out.println(new MaxWater().maxWater(new int[]{4,5,1,3,2}));
    }
}
